package cn.liulin.java8.simplestudy;

/**
 * cn.liulin.java8.simplestudy$
 *
 * @author ll
 * @date 2024-03-28 15:52:07
 **/
public class RedBlackTree {

    public Node root;

    public void put(int value) {
        if (root == null) {
            root = new Node(null, null, null, value, true);
        } else {
            Node current = root;
            Node parrent = root;
            while (current != null) {
                if (value > current.value) {
                    parrent = current;
                    current = current.right;
                } else if (value < current.value) {
                    parrent = current;
                    current = current.left;
                } else {
                    return;
                }
            }
            Node x;
            if (value > parrent.value) {
                parrent.right = new Node(parrent, null, null, value, false);
                x = parrent.right;
            } else {
                parrent.left = new Node(parrent, null, null, value, false);
                x = parrent.left;
            }
            // 处理x实际值
            fixNodeActural(x);
        }
    }

    private void fixNodeActural(Node x) {
        // 最初的判定当前节点不为null，不是根节点，且父节点的颜色是红色
        while (x != null && x != root && !isBlack(x.parent)) {
            // 如果父节点是祖父节点的左节点
            if (x.parent == x.parent.parent.left) {
                // 判断叔父节点是不是红色，是的话同时调整父节点和叔父节点还有祖父节点的颜色
                if (!isBlack(x.parent.parent.right)) {
                    x.parent.black = true;
                    x.parent.parent.black = false;
                    x.parent.parent.right.black = true;
                    x = x.parent.parent;
                } else {
                    // 如果是黑色，则需要判断当前节点是不是父节点的右节点
                    if (x == x.parent.right) {
                        x = x.parent;
                        // 左旋转
                        rolateLeft(x);
                    }
                    // 设置父节点为黑色，对祖父设置为红色，且右旋转
                    x.parent.black = true;
                    x.parent.parent.black = false;
                    Node dealX = x.parent.parent;
                    rolateRight(x.parent.parent);
                    x = dealX;
                }
            } else {
                // 如果父节点是祖父节点的右节点
                // 判断叔父节点是不是红色，是的话同时调整父节点和叔父节点还有祖父节点的颜色
                if (!isBlack(x.parent.parent.left)) {
                    x.parent.black = true;
                    x.parent.parent.black = false;
                    x.parent.parent.left.black = true;
                    x = x.parent.parent;
                } else {
                    // 如果是黑色，则需要判断当前节点是不是父节点的左节点
                    if (x == x.parent.left) {
                        x = x.parent;
                        // 右旋转
                        rolateRight(x);
                    }
                    // 设置父节点为黑色，对祖父设置为红色，且左旋转
                    x.parent.black = true;
                    x.parent.parent.black = false;
                    Node dealX = x.parent.parent;
                    rolateLeft(x.parent.parent);
                    x = dealX;
                }
            }
        }
        root.black = true;
    }

    public void delete(int value) {
        Node node = findNodeByValue(value);
        if (node == null) {
            throw new RuntimeException("无法找到删除节点");
        }
        // 判断存在几个子节点
        Node p = node;
        if (node.left != null && node.right != null) {
            // 两个子节点，则找后继节点
            Node sussor = node.right;
            while (sussor.left != null) {
                sussor = sussor.left;
            }
            // 后继节点的内容覆盖掉
            p.value = sussor.value;
            p = sussor;
        }

        // 获取替代节点
        Node replaceNode = p.left != null ? p.left : p.right;
        if (replaceNode != null) {
            // 开始替换

        } else if (p.parent == null) {
            // 也不存在父级节点了
            root = null;
        } else {
            // 没有左右节点，删除本身
            if (p.black) {
                fixDeleteActural(p);
            }
            if (p == p.parent.left) {
                p.parent.left = null;
            } else {
                p.parent.right = null;
            }
            p.parent = null;
        }
    }

    private void fixDeleteActural(Node p) {

    }

    private Node findNodeByValue(int value) {
        if (root == null) {
            return null;
        }
        Node currentNode = root;
        while (currentNode != null) {
            if (value > currentNode.value) {
                currentNode = currentNode.right;
            } else if (value < currentNode.value) {
                currentNode = currentNode.left;
            } else {
                return currentNode;
            }
        }
        return null;
    }

    private void rolateLeft(Node x) {
        // 一定存在
        Node x3 = x.right;
        // 可能为null
        Node x1 = x.parent;
        // 可能为Null
        Node x4 = x3.left;
        x3.parent = x1;
        if (x1 == null) {
            root = x3;
        } else if (x1.left == x) {
            x1.left = x3;
        } else {
            x1.right = x3;
        }
        x.parent = x3;
        x3.left = x;
        x.right = x4;
        if (x4 != null) {
            x4.parent = x;
        }
    }

    private void rolateRight(Node x) {
        // 一定存在
        Node x3 = x.left;
        // 可能为null
        Node x1 = x.parent;
        // 可能为null
        Node x4 = x3.right;
        x3.parent = x1;
        if (x1 == null) {
            root = x3;
        } else if (x1.right == x) {
            x1.right = x3;
        } else {
            x1.left = x3;
        }
        x.parent = x3;
        x3.right = x;
        x.left = x4;
        if (x4 != null) {
            x4.parent = x;
        }
    }

    protected boolean isBlack(Node x) {
        return x == null || x.black;
    }


    public class Node {
        public Node parent;
        public Node right;
        public Node left;
        public int value;
        public boolean black = true;

        public Node(Node parent, Node right, Node left, int value, boolean black) {
            this.parent = parent;
            this.right = right;
            this.left = left;
            this.value = value;
            this.black = black;
        }
    }

    protected void outByBefore(Node current) {
        if (current != null) {
            System.out.print(current.value + " ");
            outByBefore(current.left);
            outByBefore(current.right);
        }
    }

    protected void outByMiddle(Node current) {
        if (current != null) {
            outByMiddle(current.left);
            System.out.print(current.value + " " + current.black);
            outByMiddle(current.right);
        }
    }

    protected void outByAfter(Node current) {
        if (current != null) {
            outByAfter(current.left);
            outByAfter(current.right);
            System.out.print(current.value + " ");
        }
    }

    public static void main(String[] args) {
        RedBlackTree redBlackTree = new RedBlackTree();
        redBlackTree.put(1);
        redBlackTree.put(2);
        redBlackTree.put(3);
        redBlackTree.put(4);
        redBlackTree.put(5);
        redBlackTree.put(6);
        redBlackTree.put(7);
        redBlackTree.outByMiddle(redBlackTree.root);
    }
}
